The architectural specification of many microprocessors (for example x86 architecture microprocessors) requires instructions to write their results to architecturally visible state in program order (commonly referred to as in-order retirement). Nevertheless, the microarchitecture of many modern in-order retire microprocessors execute (i.e., generate instruction results) out of program order (commonly referred to as out-of-order execution). These microprocessors commonly employ a hardware structure referred to as a reorder buffer (ROB), or some similar structure, to accomplish in-order retirement in the presence of out-of-order execution.
The ROB stores information about each unretired instruction within the processor. An unretired instruction is an instruction that has been fetched, decoded, and either executed (i.e., execution units have generated its result) or waiting to be issued for execution, but its results have not yet been written to architectural state. In particular, the ROB stores information that identifies the program order of the unretired instructions relative to one another. Additionally, the ROB stores a great deal of other information about each unretired instruction.
All microprocessors include in their instruction sets branch instructions. Generally, a processor fetches instructions sequentially. However, a branch instruction instructs the processor to begin fetching instructions from a non-sequential location. Because instructions are fetched at the top of a microprocessor pipeline but executed (i.e., the branch direction and target address outcome is determined) near the bottom of the pipeline, the presence of branch instructions may result in pipeline bubbles that causes poor utilization of microprocessor resources and increased clocks per instruction (CPI), as is well-known in the art of microprocessor design.
To overcome this problem, modern microprocessors include branch predictors that predict the presence and outcome of branch instructions as they are fetched. Branch prediction is also well-known in the art of microprocessor design. However, a relatively large amount of information must be retained for the branch instruction as it is processed by the pipeline. In particular, information must be retained for the purpose of correcting a misprediction of a branch instruction and for updating the branch history information in the branch predictors to enable them to make more accurate predictions of future executions of the branch instruction. The number of bits of branch information associated with each branch instruction that must be stored can be on the order of 200 bits. Furthermore, the number of ROB entries that must store these bits can be significant, and as the execution resources of the microprocessor increases, the number of entries of the ROB will likely also need to increase significantly to fully utilize the execution resources. Thus, the storage for the branch information bits makes the ROB very large in terms of die area and power consumption.